{\magonebf 4.4 Dictionary Arrays (d\_array)}

An instance $A$ of the data type $d\_array$ (dictionary array) is an 
injective mapping from a linearly ordered data type $I$, called the index 
type of $A$, to a set of variables of a data type $E$, called the element 
type of $A$. 


\bigskip
{\bf 1. Declaration of a d\_array type}


\decltwo d\_array I E 

introduces a new data type with name \name\ consisting of all d\_arrays 
with index type $I$ and element type $E$. \precond $I$ is linearly ordered.



\bigskip
{\bf 2. Creation of a d\_array }


\create A (x)

creates an injective function $a$ from $I$ to the set of unused variables of 
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
with $a$.



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 5truecm &\cr
\+\opa E\&   {I\ x}  
                      {returns the variable $A(x)$}
\smallskip
\+\op bool   defined {I\ x}
                      {returns true if $x \in dom(A)$, false otherwise; here}
\+\nop                {$dom(A)$ is the set of all $x\in I$ for which $A[x]$ has}
\+\nop                {already been executed.}

\bigskip
{\bf 4. Iteration}

{\bf forall\_defined}($x,A$) 
$\{$ ``the elements from $dom(A)$ are successively assigned to $x$'' $\}$


\bigskip
{\bf 5. Implementation}

Dictionary arrays are implemented by red black trees. Access operations $A[x]$
take time $O(\log dom(A))$. The space requirement is $O(dom(A))$.


\vfill\eject
{\bf 6. Example}
\bigskip
\input prog/d_array.prog

